package algorithm.dynamicProgramming.p72;

class Solution1 {
    private int[][] memo;
    public int minDistance(String word1, String word2) {
        int length1 = word1.length();
        int length2 = word2.length();
        memo = new int[length1][length2];
        return dp(length1 - 1, length2 - 1, word1, word2);
    }

    private int dp(int i, int j, String word1, String word2) {
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;
        if(memo[i][j] != 0) return memo[i][j];
        if(word1.charAt(i) == word2.charAt(j))
            memo[i][j] = dp(i - 1, j - 1, word1, word2); // 什么都不做
        else {
            memo[i][j] = Math.min(dp(i, j - 1, word1, word2), 
            Math.min(dp(i - 1, j, word1, word2), dp(i - 1, j - 1, word1, word2))) + 1;
        }
        return memo[i][j]; 
    }
}